package org.example.algorithm.array;

import java.util.ArrayList;
import java.util.List;

public class CombinationSum3Solution {
    private List<List<Integer>> list = new ArrayList<>();

    public static void main(String[] args) {
        CombinationSum3Solution solution = new CombinationSum3Solution();
        List<List<Integer>> res = solution.combinationSum3(3, 8);
        System.out.println(res);
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        if (n < 1 || n > 45) {
            return list;
        }
        List<Integer> combination = new ArrayList<>();
        dfs(arr, n, k, 0, combination);
        return list;
    }

    private void dfs(int[] arr, int n, int k, int index, List<Integer> combination) {
        if (k == 0 || index == arr.length) {
            if (n == 0 && k == 0) {
                list.add(new ArrayList<>(combination));
            }
            return;
        }
        //当前索引不选
        dfs(arr, n, k, index+1, combination);
        //当前索引选择
        combination.add(arr[index]);
        dfs(arr, n-arr[index], k-1, index+1, combination);
        combination.remove(combination.size()-1);
    }
}
